package leetcode.D400.T381;

import java.util.*;

/**
 * @File Info: leetcode -- <RandomizedCollection>
 * @Author: 18362
 * @Create: 2022-03-10 13:29:38 星期四
 */

class RandomizedCollection {

    private Map<Integer, Set<Integer>> map = new HashMap<>();
    private List<Integer> list = new ArrayList<>();
    private Random random = new Random(System.currentTimeMillis());

    public RandomizedCollection() {

    }

    public boolean insert(int val) {
        list.add(val);
        if (map.containsKey(val)) {
            map.get(val).add(list.size()-1);
            return false;
        }
        Set<Integer> set = new HashSet<>();
        set.add(list.size()-1);
        map.put(val, set);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val))
            return false;
        Set<Integer> set = map.get(val);
        Iterator<Integer> it = set.iterator();
        int loc = it.next();
        set.remove(loc);
        if (set.size()==0)
            map.remove(val);
        delete(loc);
        return true;
    }

    private void delete(int loc) {
        if (loc == list.size()-1) {
            list.remove(list.size()-1);
            return;
        }
        int val = list.get(list.size()-1);
        Set<Integer> set = map.get(val);
        set.remove(list.size()-1);
        list.remove(list.size()-1);
        list.set(loc, val);
        set.add(loc);
    }

    public int getRandom() {
        int loc = random.nextInt(list.size());
        return list.get(loc);
    }
}